package alo.p6.work;

import alo.p6.BinaryTreeNode;

import java.util.LinkedList;
import java.util.Queue;

//找到二叉树中层数据和最大的层
public class FindLevelWithMaxSum {
    //与非递归求二叉树深度的方法相似
    int findLevelWithMaxSum(BinaryTreeNode root){
        BinaryTreeNode temp;
        int level=1,maxlevel=0;
        Queue<BinaryTreeNode> queue=new LinkedList<>();
        int currentSum=0,maxSum=0;
        if (root==null) return 0;
        queue.offer(root);
        queue.offer(null);
        while (!queue.isEmpty()){
            temp=queue.poll();
            if (temp==null){
                if (currentSum>maxSum){
                    maxSum=currentSum;
                    maxlevel=level;
                }
                currentSum=0;
                if (!queue.isEmpty())
                    queue.offer(null);
                level++;
            }else {
                currentSum+=temp.getData();
                if (temp.getLeft()!=null) queue.offer(temp.getLeft());
                if (temp.getRight()!=null) queue.offer(temp.getRight());
            }
        }
        return maxlevel;
    }
}
